The amount of data transmitted over telecommunications networks increases rapidly. High speed and high capacity packet data networks and servers are employed for transferring these data. Amongst others for test and monitoring purposes, to guarantee a desired or agreed Quality of Service, QoS, for example, packet header information on, for example, source and destination addresses is not sufficient to obtain the required information. In some cases the payload of data packets needs to be inspected for particular data patterns, for example. Data mining, detection of data viruses and other malicious data are further examples that may require packet data inspection.
A method of inspecting packets is by employing finite automata, such as disclosed in US 2008/270764 A1 and EP 1 986 390 A2. A finite automata, or simply a state machine, is a computer controlled method that is employed as an abstract state machine operating on states according to a state transition table or state transition register. Such state transition table comprises—for a plurality of states of the finite automata—a transition from a present, initial state to a next, destination state upon inputting a particular data symbol in the present state, eventually leading to a data pattern match of a particular string of input data symbols. Such data symbols are, for example, the data symbols comprised in an alphabet such as the well-known computer alphabet American Standard Code for Information Interchange, or in short ASCII. As such, a state transition to a subsequent, destination state may also involve a transition to the same state of the automata, called a non-forwarding transition. In such a case, the state transition is a transition wherein the initial state equals the destination state, e.g., a non-forwarding loop to the same state.
In general, two types of finite automata can be distinguished. Deterministic Finite Automata, DFA, and Non-deterministic Finite Automata, NFA. DFA is preferred at processing speed, as it requires only constant amount of memory accesses while parsing thru the packet payload. The cost of such computation efficiency is the high memory storage as the number of states and state transitions exponentially increases memory footprint. NFA has lower memory storage requirements but as from every state the next state can be several others in parallel, it requires a lot of computation resources to check every possible case.
Both DFA and NFA have their own strengths and weaknesses and can be employed in software tools for data packet inspection systems.
As the amount of data transmitted over telecommunications networks increases rapidly, network servers employing a finite automata may require a too high amount of resources, i.e. memory storage and memory access controllers, generally designated as memory footprint. Accordingly, there is a need for an improved method of detecting data patterns by executing finite automata.